In recent times there has been a trend in wireless communications towards ad-hoc networks where telecommunications and computing devices (such as PCs, pagers and mobile phones) are intended to be freed from fixed or subscription-based cellular networks so as to have flexible operability and modality.
One such example described on the Bluetooth™ web site (http:\\bluetooth.com) is the ‘three-in-one’, which can operate in the home as a cordless phone, outside the home as a mobile (cellular) phone, and as a two-way walkie talkie device. This illustrates the ad-hoc nature of the radio links that may be formed.
Although the following discussion focuses on Bluetooth™, it will be appreciated that the invention has general application to other forms of frequency hopping-based ad-hoc networks.
Reference can be made to the Bluetooth™ Core Specification Volume 1, Version 1.0B (available from the noted web site).
Bluetooth™ technology allows for the formation of networks called piconets and interconnection of such networks, called scatternets without the involvement of a central infrastructure, in an ad-hoc fashion. This is made possible using distributed algorithms for inquiry and paging. While device discovery in this document refers to the process of obtaining Bluetooth™ addresses and clocks of neighboring devices using inquiry procedures, paging is used to setup a connection with a particular Bluetooth™ device.
The Bluetooth™ physical layer uses frequency hopping which conforms to FCC regulations for the 2.4 GHz ISM band. It uses a 79 hop system with each hop occupying 1 MHz. These restrictions have implications on the device discovery process. One implication is: when a device wakes up to scan for inquiry messages, it cannot do so at a fixed dedicated frequency. Instead, the wake up frequency could be any of the 32 frequencies in the inquiry hopping sequence. The actual frequency used depends upon the clock of the scanning device, which is not known to the inquirer. Moreover, since the onus of finding a new device is deliberately kept with the inquirer, the scanning device does not do continuous scanning. Hence, in the inquiry procedure there is uncertainty in both time and frequency at which the scanning device(s) might be listening.
The Baseband Specifications of the Bluetooth™ Version 1.0 specifications specify device discovery procedures (henceforth called the BT algorithms) using inquiry and inquiry scan in which the inquirer has no information about the address or clock of the devices around it. The procedures work well when there are no simultaneous inquirers. The performance is difficult to predict in the case of multiple simultaneous inquirers.
Due to the above factors, the inquiry procedure becomes time and energy consuming for the device doing inquiry. Even in an error-free environment, it can take 10.24 sec for an inquiring device to collect all responses. These delays could be bottlenecks in setting up individual connections and ad-hoc networks. Many application scenarios envisioned for Bluetooth™ require a large number of terminals to operate in overlapping areas. Under such conditions even the average delays are increased, prohibiting the use of the technology for these applications. Some modifications to the device discovery algorithms are thus required which can enable such applications by a reduction of these delays.
Due to the interaction of several devices during inquiry, the problem of finding the delay distribution or even average delays is not easily tractable. These delays depend upon the number of devices participating in an inquiry procedure, the number of inquiring devices, the bandwidth reserved for inquiry, the number of responses required from an inquiry, etc.
It is an object of the invention to provide a device discovery procedure which results in a faster exchange of inquiry responses than in the prior art, in a system having multiple simultaneous inquirers, yet maintaining performance otherwise.